package com.breeze.leetcode;

/**
 * https://leetcode-cn.com/problems/minimum-path-sum/
 * 64. 最小路径和
 * 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 * <p>
 * 说明：每次只能向下或者向右移动一步。
 * <p>
 * 输入:
 * [
 * [1,3,1],
 * [1,5,1],
 * [4,2,1]
 * ]
 */

import kotlin.Pair;

import java.util.HashMap;
import java.util.Map;

/**
 * 动态规划
 * 1. 最右子结构、无后效性  ： F(m,n) 与 F(m-1,n) 和 F(m,n-1)有关
 * 2. 状态转移方程 ：F(m,n) = min{F(m-1,n), F(m,n-1)} + grid[m-1][n-1] , ()
 * 3. 边界条件：F(0,0) = grid[0]
 */
public class LeetCode64 {
    /**
     * 1. 递归方式 + 备忘录    如果不采用备忘录，leetcode执行会超时
     * 即使这样时间性能和空间性能很低，也是刚通过Leetcode的标准
     */
    public int minPathSum(int[][] grid) {
        return minPathSum(grid, grid.length, grid[0].length);
    }

    Map<Pair, Integer> memo = new HashMap<>();


    private int minPathSum(int[][] grid, int m, int n) {
        Pair<Integer, Integer> pair = new Pair<>(m, n);
        if (memo.containsKey(pair)) {
            return memo.get(pair);
        }
        if (m == 1 && n == 1) {
            return grid[0][0];
        }
        int up = 0;
        if (m > 1) {
            up = minPathSum(grid, m - 1, n);
        }
        int left = 0;
        if (n > 1) {
            left = minPathSum(grid, m, n - 1);
        }

        int temp = m <= 1 ? left : n <= 1 ? up : Math.min(up, left);
        int res = temp + grid[m - 1][n - 1];
        memo.put(pair, res);
        return res;
    }


    /**
     * 2. 动态规划
     * <p>
     * -> 状态定义： 设 dp 为大小mxn的矩阵 其中dp[i][j] 表示从(0,0)走到(i,j)位置的最小路径数字总和
     * -> 状态转移方程： dp[i][j] = min(dp[i-1,j],dp([i],[j-1]) + grid[i,j]
     * -> 加入边界条件考虑，状态转移方程最终形态：
     * 1. 当左边和上边都不是矩阵边界时： dp[i][j] = min(dp[i-1,j],dp([i],[j-1]) + grid[i,j], (i!=0,j!=0)
     * 2. 当只有左边为矩阵边界时： dp[i][j] = dp[i-1,j] + grid[i][j]，(j=0,i!=0)
     * 3. 当只有上边为矩阵边界时： dp[i][j] = dp[i,j-1] + grid[i][j] ,(i=0,j!=0)
     * 4. 当左上均为矩阵边界时： dp[i][j] = grid[i][j],(i=0,j=0)
     * <p>
     * -> 初始状态： dp初始化即可，默认值为0即可
     * -> 返回值： 返回 dp 矩阵右下角值，即走到终点的最小路径数字和
     * <p>
     * <p>
     * 可以通过grid矩阵代替dp矩阵节省空间消耗，原grid矩阵虽然会被dp矩阵元素覆盖，但覆盖元素处于grid矩阵i,j的左上方，故不会影响i,j增大后的dp计算。
     * <p>
     * 时间复杂度：O(mxn)
     * 空间复杂度：O(1)
     */
    public int minPathSum1(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (i == 0 && j == 0) continue; // 左上均为矩阵边界
                else if (j == 0) grid[i][j] = grid[i - 1][j] + grid[i][j];// 左边为矩阵界
                else if (i == 0) grid[i][j] = grid[i][j - 1] + grid[i][j];  // 上边为矩阵边界
                else grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]; // 非矩阵边界
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }

    public static void main(String[] args) {
        LeetCode64 leetCode64 = new LeetCode64();
        int[][] grid = {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1},
        };
        System.out.println(leetCode64.minPathSum1(grid));
    }
}
